1. Field of the Invention
The present invention relates to method and apparatus for saving space in a translation lookaside buffer. More specifically, the present invention relates to method and apparatus for saving memory space without compromising the performance of a translation lookaside buffer within the central processing unit (CPU).
2. Art Background
It is quite common for a fast central processor unit to have a cache memory in addition to a main computer memory. The cache memory is smaller, but much faster than the main computer memory. It is placed between the processor and the main memory. During the execution of the software program, the cache memory stores the most frequently utilized instructions and data. Whenever the processor needs to access information from memory, the processor examines the cache first before accessing the main computer memory. A cache miss occurs if the processor cannot find instructions or data in the cache memory and is required to access the slower main memory. Thus, the cache memory reduces the average memory access time of the processor. For further information on cache memories, please refer to Alan J. Smith's article on Cache Memories, Computing Survey, Vol. 14, No. 3, September 1982.
Virtual addressing provides increased flexibility and capability to a system. For example, through virtual addressing a larger address space is achieved as well as insolation of the software from physical addressing by providing a virtual address space in which the software operates. In order to implement virtual addressing, a mechanism is needed to translate the virtual addresses to physical addresses. Many CPUs contain a translator, which translates virtual addresses to physical memory addresses, and a translation lookaside buffer (TLB), which caches recently generated virtual-physical address pairs. The TLBs are essential because they allow faster access to the main memory by skipping the mapping process when the translation pairs already exist.
The operation of a cache begins with the arrival of a virtual address, usually from the CPU, and the appropriate control signal. The virtual address is passed to both the TLB and the cache memory. The TLB accepts the virtual page number and uses it to select a set of elements, which is then searched associatively for a match to the virtual address. If a match is found, the corresponding physical address is passed to the comparator to determine whether the data is in the cache.
If the TLB does not contain the virtual-physical address pair needed for the translation, then the address translator is invoked. The translator uses the high-order bits of the virtual address as an entry into the segment and page tables, which may be in either the cache or the main memory, for the process and then returns the address pair to the TLB, thus replacing an existing TLB entry.
A TLB entry contains a number of fields. The virtual address presented for translation is matched against the virtual address tag field in the TLB to ensure that the right entry has been found. The virtual address tag field contains an Address Space Identifier (ASID) so that entries for more than one process can be in the TLB at one time. In some machines such as the IBM 370, a protection field is included and is checked to ensure that the access is permitted.
There is also a bit in the TLB that indicates whether a given entry in the TLB is valid. This bit is called a Valid bit. As each entry is entered into the TLB, the corresponding valid bit in the entry is set. During a TLB compare function, if the status of the valid bit is reset, then no compare takes place for that entry. If the valid bit is set, then a compare function can proceed. In some TLB designs, there are bits allocated to indicate the length of the virtual address in the virtual address tag to be compared, since each length may represent a different function.
Because some TLBs are content addressable memories (CAM), they are usually four times as large as their random access memory (RAM) counterpart. This is due to the built-in associative mathematical logic in the transistors, which operate a "compare" function instead of a "hold" function. Therefore, it becomes highly desirable to conserve space in the TLB CAM without any impact on its performance.